package com.sfx.算法专题.位运算;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-21
 * Time: 15:20
 */
public class Code_8_missingTwo {
    static class Solution {
        public int[] missingTwo(int[] nums) {
            // 这个题目其实就是丢失的数字 + 只出现一次的数字3结合的
            // 首先我们要找出丢失的两个数字
            // 步骤就是将nums中的和1~N中的数字全部异或在一起
            // 最终的结果就是 a ^ b 和一堆抵消的数字
            // 我们只需要把a和b拆分出来即可==>只出现一次的数字3
            // 如何进行拆分?
            // 找到k位置->该位置为1=>两个数字的该比特位不同
            // 然后进行分组
            // 对所有的数字(1~N和nums中的)该比特位为1 ^ 上num1
            // 对所有的数字(1~N和nums中的)该比特位为0 ^ 上num2
            // 最终该比特位上的其他数字都抵消了就剩下丢失的数字了,nums1和nums2

            // 找到丢失的两个数字的结合
            int sum = 0;
            for (int num : nums) {
                sum ^= num;
            }

            for (int i = 1; i <= nums.length + 2; i++) {
                sum ^= i;
            }

            // 进行拆分
            int lowb = sum & (-sum);
            int num1 = 0, num2 = 0;
            for (int num : nums) {
                if ((num & lowb) == 0)
                    num1 ^= num;
                else
                    num2 ^= num;
            }

            for (int i = 1; i <= nums.length + 2; ++i) {
                if ((i & lowb) == 0)
                    num1 ^= i;
                else
                    num2 ^= i;
            }
            return new int[]{num1, num2};
        }
    }
}